package phaseI;

//import java.nio.CharBuffer;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;


public class NFACombiner {

	//Regex operations
	public static final int OR = 1;
	public static final int QUESTIONMARK = 2;
	public static final int PLUS = 3;
	public static final int ASTERISK = 4;
	public static final int CONCAT = 5;
	public static final int OPENPAREN = 6;
	public static final int CLOSEPAREN = 7;
	
	public static final String OPS = "+*?";
	public static final String IN = "IN";
	
	private static int depth = 0;
	
	public static NFATable combineNFAs(NFATable left, NFATable right, int operation)
	{
		NFATable result = new NFATable();
		if(operation == OR)
		{
			result.addState("1");
			transferStates(result, left);
			transferStates(result, right);
			result.addTransition("1", "2", "epsilon");
			result.addTransition("1", left.getStateCount() + 2 + "", "epsilon");
		}
		else if(operation == CONCAT)
		{
			transferStates(result,left);
			result.clearEndStates();
			transferStates(result,right);
			for(String endState : left.getEndStates())
			{
				result.addTransition(endState,left.getStateCount()+1+"","epsilon");
			}
		}
		else
			result = null;
		
		return result;
	}
	
	public static NFATable applyQuantification(NFATable initial, int operation)
	{
		NFATable result = new NFATable();
		if(operation == QUESTIONMARK)
		{
			result.addState("1");
			transferStates(result, initial);
			result.addTransition("1", "2", "epsilon");
			//state for zero quantities of regex expression
			String zeroState =  initial.getStateCount() + 2 + "";
			result.addTransition("1",zeroState, "epsilon");
			result.addEndState(zeroState);
		}
		if(operation == PLUS)
		{
			transferStates(result, initial);
			for(String endState : result.getEndStates())
				result.addTransition(endState, "1", "epsilon");
		}
		if(operation == ASTERISK)
		{
			result = applyQuantification(initial,PLUS);
			result = applyQuantification(result,QUESTIONMARK);
		}
		if(operation == OPENPAREN)
		{
			//(a(b|c)*)|(a))
			depth--;
			//recurse out
		}
		if(operation == CLOSEPAREN)
		{
			depth++;
		}
		return result;
	}
	
	public static NFATable transferStates(NFATable receiver, NFATable holder)
	{
		
		Hashtable<String,Hashtable<String,ArrayList<String>>> table = holder.getTable();		
		Iterator<Map.Entry<String,Hashtable<String,ArrayList<String>>>> iterStates = table.entrySet().iterator();
		int stateCount = receiver.getStateCount();
		while(iterStates.hasNext())
		{
			Map.Entry<String,Hashtable<String,ArrayList<String>>> entry = iterStates.next();
			Iterator<Map.Entry<String,ArrayList<String>>>iterTrans = entry.getValue().entrySet().iterator();
			while(iterTrans.hasNext())
			{
				Map.Entry<String,ArrayList<String>> entryTrans = iterTrans.next();
				ArrayList<String> nextStates = entryTrans.getValue();
				for(String nextState : nextStates)
				{
					receiver.addTransition(stateCount + Integer.parseInt(entry.getKey()) + "", stateCount + Integer.parseInt(nextState) + "", entryTrans.getKey());
				}
			}
		}	
		for(String endState : holder.getEndStates())
		{
			receiver.addEndState(stateCount + Integer.parseInt(endState) + "");
		}
		return receiver;
	}
	
//	public static NFATable navigateTree(SyntaxTree tree)
//	{
//		recurseNode(tree.root,false);
//		return null;
//	}
//	
//	public static NFATable recurseNode(TreeNode node, boolean bracketMode)
//	{
//		for(TreeNode child : node.children)
//		{
//			System.out.println("Recurse");
//			boolean switchMode = (bracketMode | child.getData().equals("[")) && !child.getData().equals("]");
//			System.out.println(child.getData());
//			recurseNode(child,switchMode);
//			
//		}
//		System.out.println("Return");
//		return null;
//	}
	
	public static NFATable navigateTreeWithStack(SyntaxTree tree)
	{
		TreeNode current = tree.root;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		
		stack.push(current);
		
		boolean bracketMode = false;
//		boolean caretMode = false;
		
		NFATable result = null;
		NFATable lastTable = new NFATable();
		String lastOperator = "";
		String previousOperator = "";
		
		LinkedList<Character> currentBracketAlphabet = new LinkedList<Character>();
		LinkedList<Character> previousBracketAlphabet = new LinkedList<Character>();
		String lastChar = "";
		String lastChar2 = "";
		boolean wasDash = false;
		boolean containsCARET = false;
		boolean justFinishedBracket = false;
		boolean createdNewTable = false;
		boolean createdBracketTable = false;
		boolean opTable = false;
		boolean concat = false;
		
		//TODO create lookahead for quantification variables
		String futureOp = "";
		
		while(!stack.isEmpty())
		{
			current = stack.pop();
//			System.out.println(current);
//			for(int i = current.children.size()-1;i>=0;i--){
//				stack.push(current.children.get(i));
//			}
//			
			for(TreeNode child : current.children)
			{
				stack.push(child);
			}
			opTable = !futureOp.equals("");
//			System.out.println(opTable);
			String data = current.getData();
			if(!data.isEmpty()){
				bracketMode = ("]".equals(data) || bracketMode) && !"[".equals(data);
//				if(justFinishedBracket)
//				{
//					if(!IN.equals(data))
//					{
//						NFATable alpha = new NFATable();
//						int chStateCount = 2;
//						for(char ch : previousBracketAlphabet)
//						{
//							alpha.addTransition("1", chStateCount + "",ch + "");
//							alpha.addEndState(chStateCount + "");
//							chStateCount++;
//						}
//						lastTable=alpha;
//						createdNewTable=true;
//						createdBracketTable=true;
//						//System.out.println(lastTable.toString());
//					}
//					justFinishedBracket=false;
//				}
				if(bracketMode && !"]".equals(data))
				{
					//System.out.println("In bracket mode");
					if("-".equals(data))
					{
						wasDash=true;
					}
					else if (wasDash)
					{
						//System.out.println(data.charAt(0));
						for(char i = data.charAt(0); i <= lastChar.charAt(0);i++)
						{
							if(!currentBracketAlphabet.contains(i))
								currentBracketAlphabet.add(i);
						}
						wasDash=false;
						lastChar="";
					}
					else if (".".equals(data))
					{
						for(char i = 0; i <= 127;i++)
						{
							if(i!='\n' && !currentBracketAlphabet.contains(i))
								currentBracketAlphabet.add(i);
						}

					}
					else if ("^".equals(data))
					{
						containsCARET = true;
						if(!"".equals(lastChar) && !currentBracketAlphabet.contains(lastChar.charAt(0)))
							currentBracketAlphabet.add(lastChar.charAt(0));
						//System.out.println(currentBracketAlphabet);
					}
					else
					{
						
						if(!"".equals(lastChar) && !currentBracketAlphabet.contains(lastChar.charAt(0)))
							currentBracketAlphabet.add(lastChar.charAt(0));
						//System.out.println(lastChar.charAt(0));
						lastChar=data;
					}
				}
				else if("[".equals(data))
				{
					//System.out.println(stack.peek());
					if((stack.isEmpty() || !stack.peek().getData().equals(IN) ) && !containsCARET)
					{
//						System.out.println("no in");
						NFATable alpha = new NFATable();
						int chStateCount = 2;
						for(char ch : currentBracketAlphabet)
						{
							alpha.addTransition("1", chStateCount + "",ch + "");
							alpha.addEndState(chStateCount + "");
							chStateCount++;
						}
						lastTable=alpha;
						currentBracketAlphabet=new LinkedList<Character>();
						createdNewTable=true;
					}
					if(containsCARET)
					{
//						System.out.println(previousBracketAlphabet);
//						System.out.println(currentBracketAlphabet);
						containsCARET=false;
						NFATable alpha = new NFATable();
						int chStateCount = 2;
						for(char ch : previousBracketAlphabet)
						{
							if(!currentBracketAlphabet.contains(ch))
							{
								alpha.addTransition("1", chStateCount + "",ch + "");
								alpha.addEndState(chStateCount + "");
								chStateCount++;
							}
						}
						lastTable=alpha;
						createdNewTable=true;
						//System.out.println(currentBracketAlphabet);
						//System.out.println(lastTable.toString());
					}
//					else
//					{
//						justFinishedBracket=true;
//					}
//					System.out.println("EndBracket");
					previousBracketAlphabet=(LinkedList<Character>)currentBracketAlphabet.clone();
					//System.out.println(previousBracketAlphabet.toString());
					currentBracketAlphabet=new LinkedList<Character>();
				}

				else if (!"]".equals(data))
				{
					System.out.println(data);
					if("|".equals(data))
					{
						previousOperator=lastOperator;
						lastOperator=data;
					}
					else if(OPS.contains(data))
					{
						futureOp = data;
					}
					else if(!IN.equals(data))
					{
						NFATable table = new NFATable();
						table.addTransition("1", "2", data);
						table.addEndState("2");
						lastTable = table;
						createdNewTable=true;
						if(!OPS.contains(lastChar2) && !IN.equals(lastChar2) && ! "|".equals(data))
						{
							concat = true;
						}
						
					}
				}
			}
			if(createdNewTable)
			{
				if(result==null)
					result = lastTable;
				else
				{
					if(concat)
					{
						result = NFACombiner.combineNFAs(lastTable, result, CONCAT);
						concat=false;
					}
					if(opTable)
					{
						//System.out.println("apply");
						//System.out.println(lastTable.toString());
	
						if(futureOp.equals("?"))
						{
							lastTable = applyQuantification(lastTable, QUESTIONMARK);
						}
						else if(futureOp.equals("+"))
						{
							lastTable = applyQuantification(lastTable, PLUS);
						}
						else if(futureOp.equals("*"))
						{
							lastTable = applyQuantification(lastTable, ASTERISK);
						}
	//					else if(futureOp.equals("("))
	//					{
	//						lastTable = applyQuantification(lastTable, OPENPAREN);
	//					}
	//					else if(futureOp.equals(")"))
	//					{
	//						lastTable = applyQuantification(lastTable, CLOSEPAREN);
	//					}
						
						futureOp="";
						opTable=false;
					}
				}
				createdNewTable = false;
				if(createdBracketTable)
				{
					createdBracketTable = false;
					if(previousOperator.equals(""))
					{
						result = lastTable;
						//System.out.println(result.toString());
					}
					else if(previousOperator.equals("|"))
					{
						result = NFACombiner.combineNFAs(lastTable, result, OR);
						//System.out.println(result.toString());
					}
				}
				
				else
				{
					if(lastOperator.equals(""))
					{
						result = lastTable;
						//System.out.println(result.toString());
					}
					else if(lastOperator.equals("|"))
					{
						result = NFACombiner.combineNFAs(lastTable, result, OR);
						//System.out.println(result.toString());
					}
				}
			}
			lastChar2=data;
		}
		return result;
	}
	
}
